package leetcode101.sort;

import java.util.*;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code2
 * @Description 347. Top K Frequent Elements
 * Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
 *
 *  
 *
 * Example 1:
 *
 * Input: nums = [1,1,1,2,2,3], k = 2
 * Output: [1,2]
 * Example 2:
 *
 * Input: nums = [1], k = 1
 * Output: [1]
 *
 *
 * Constraints:
 *
 * 1 <= nums.legth <= 105
 * k is in the range [1, the number of unique elements in the array].
 * It is guaranteed that the answer is unique.
 *
 *
 * Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-29 18:25
 */
public class Code2 {
    public static void main(String[] args) {
        int[] nums = new int[]{1,1,1,2,2,3};
        topKFrequent(nums, 2);
    }
    public static int[] topKFrequent(int[] nums, int k) {
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > max) {
                max = nums[i];
            }
            if (nums[i] < min) {
                min = nums[i];
            }
        }


        TreeMap<Integer, Integer> bucket = new TreeMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (bucket.get(nums[i]) == null) {
                bucket.put(nums[i], 1);
            } else {
                bucket.put(nums[i], bucket.get(nums[i]) + 1);
            }
        }
        List<Map.Entry<Integer, Integer>> list = new ArrayList<>(bucket.entrySet());
        Collections.sort(list, (o1, o2) -> o2.getValue() - o1.getValue());
        int[] res = new int[k];
        for (int i = 0; i < res.length; i++) {
            res[i] = list.get(i).getKey();
        }
        return res;
    }

}
